package leetcode_day._2021._202108._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/29 23:07
 * 所有奇数长度子数组的和
 * 算法：前缀和
 */
public class _29_1588 {
    public static void main(String[] args) {
        System.out.println(new _29_1588().sumOddLengthSubarrays(new int[]{1, 4, 2, 5, 3}));
    }

    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] pre = new int[n];
        pre[0] = arr[0];
        for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + arr[i];
        int ans = pre[n - 1];
        for (int i = 3; i <= n; i += 2) {
            for (int j = 0; j < n; j++) {
                if (j + i - 1 < n) {
                    if (j == 0) ans += pre[j + i - 1];
                    else ans += pre[j + i - 1] - pre[j - 1];
                } else break;
            }
        }
        return ans;
    }

}
